-- 时间估算
-- 1.搞懂Lua基本语法	 30min
-- 2.算法				20min
-- 3.整理				10min
-- 4.测试				5min

function swap(a, i, j)
	local tem = a[i]
	a[i] = a[j]
	a[j] = tem
end

function merge(array1, array2)
	local lengthA, lengthB = #array1, #array2
	for i = lengthA + 1, lengthA + lengthB do
		array1[i] = array2[i - lengthA]
	end
end

--从控制台取得输入
function getArray()
	--local tem = {2, 5, 8, 9, 6, 3, 7, 4, 1}
	print("length of array")
	local string = io.read()
	local t = tonumber(string)
	print("number")
	local tem = {}
	while(true)
	do
		local line = io.read()
		local numbers = {}
		--以空格分割
		string.gsub(line, '[^'..' '..']+',  function (w)
			table.insert(numbers, tonumber(w))
		end)
		merge(tem, numbers)
		if(#tem == t) then
			break
		--多余的数删掉
		elseif(#tem > t) then
			for i = t + 1, #tem, 1 do
				tem[i] = nil
			end
			break
		end
	end
	return tem
end

function  quickSort(a, leftbound, rightbound)
	if(leftbound > rightbound) then
		return
	end
	local i = leftbound
	local j = rightbound
	local tag = a[leftbound]
	while(i ~= j)
	do
		--右侧
		while(i < j and a[j] >= tag)
		do
			j = j - 1
		end
		if(tag > a[j]) then
			swap(a, i, j)
			i = i + 1
		end
		--左侧
		while(i < j and a[i] <= tag)
		do
			i = i + 1
		end
		if(tag < a[i]) then
			swap(a, i, j)
			j = j - 1
		end
		--分别二分
		quickSort(a, leftbound, i - 1)
		quickSort(a, i + 1, rightbound)
	end
end
function show(a)
	for i = 1, #a do
		print(a[i])
	end
end

a = getArray()
quickSort(a, 1, #a)
show(a)